#include "stack_queue.h"
#include <cctype>
#include <cmath>

listNode::listNode() : next(NULL), data(0) {}
listNode::listNode(int nodeData, listNode* succ) : next(succ), data(nodeData) {}

MyStack::MyStack() : topNode(NULL) {}
MyStack::~MyStack() {
    while (topNode) {
        listNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }
}
bool MyStack::push(const int& item) {
    listNode* newNode = new listNode(item, topNode);
    topNode = newNode;
    return true;
}
bool MyStack::pop(int& item) {
    if (!topNode) return false;
    item = topNode->data;
    listNode* temp = topNode;
    topNode = topNode->next;
    delete temp;
    return true;
}
bool MyStack::getTop(int& item) {
    if (!topNode) return false;
    item = topNode->data;
    return true;
}
void MyStack::printStack() {
    listNode* p = topNode;
    while (p) {
        cout << p->data;
        if (p->next) cout << ",";
        p = p->next;
    }
    cout << endl;
}

MyQueue::MyQueue(const int& cap) : capacity(cap), front(0), rear(0) {
    queue = new int[capacity];
}
MyQueue::~MyQueue() {
    delete[] queue;
}
bool MyQueue::enQueue(const int& item) {
    if ((rear + 1) % capacity == front) return false;
    queue[rear] = item;
    rear = (rear + 1) % capacity;
    return true;
}
bool MyQueue::deQueue(int& item) {
    if (front == rear) return false;
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}
bool MyQueue::getFront(int& item) {
    if (front == rear) return false;
    item = queue[front];
    return true;
}
void MyQueue::printQueue() {
    int i = front;
    while (i != rear) {
        cout << queue[i];
        if ((i + 1) % capacity != rear) cout << ",";
        i = (i + 1) % capacity;
    }
    cout << endl;
}
bool MyQueue::isFull() {
    return (rear + 1) % capacity == front;
}
bool MyQueue::isEmpty() {
    return front == rear;
}

bool postfixExpression(const string& infix, string& result) {
    MyStack stack;
    string postfix;
    for (char c : infix) {
        if (isdigit(c)) {
            postfix += c;
        }
        else if (c == '(') {
            stack.push(c);
        }
        else if (c == ')') {
            int top;
            while (stack.pop(top) && top != '(') {
                postfix += ' ';
                postfix += static_cast<char>(top);
            }
            if (!stack.getTop(top) || top != '(') {
                result = "Expression is wrong!";
                return false;
            }
            stack.pop(top);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            int precedence = (c == '*' || c == '/') ? 2 : 1;
            int top;
            while (!stack.isEmpty() && stack.getTop(top) &&
                (top == '*' || top == '/' ||
                    (top == '+' || top == '-' && precedence <= 1))) {
                postfix += ' ';
                postfix += static_cast<char>(top);
                stack.pop(top);
            }
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        int top;
        if (!stack.pop(top)) {
            result = "Expression is wrong!";
            return false;
        }
        if (top == '(') {
            result = "Expression is wrong!";
            return false;
        }
        postfix += ' ';
        postfix += static_cast<char>(top);
    }
    result = postfix;
    return true;
}

bool expressionVal(const string& postfix, int& result) {
    MyStack stack;
    for (char c : postfix) {
        if (isdigit(c)) {
            stack.push(c - '0');
        }
        else if (c == ' ') {
            continue;
        }
        else {
            int b, a;
            if (!stack.pop(b) || !stack.pop(a)) return false;
            switch (c) {
            case '+': stack.push(a + b); break;
            case '-': stack.push(a - b); break;
            case '*': stack.push(a * b); break;
            case '/':
                if (b == 0) return false;
                stack.push(a / b);
                break;
            default: return false;
            }
        }
    }
    if (!stack.isEmpty()) {
        stack.pop(result);
        return true;
    }
    return false;
}

void yanghui(const int& n) {
    MyQueue queue;
    queue.enQueue(1);
    for (int i = 1; i <= n; i++) {
        int prev = 0;
        for (int j = 0; j < i; j++) {
            int current;
            queue.deQueue(current);
            cout << prev + current;
            if (j < i - 1) cout << ",";
            queue.enQueue(prev + current);
            prev = current;
        }
        queue.enQueue(1);
        cout << endl;
    }
}